package com.suzhenyu.sort;

/**
 * quickSort 快速排序
 * @author suzy2
 */
public class QuickSort implements Sort{
    /**
     * （类似于选择排序的定位思想）选一基准元素，
     * 依次将剩余元素中小于该基准元素的值放置其左侧，
     * 大于等于该基准元素的值放置其右侧；
     * 然后，取基准元素的前半部分和后半部分分别进行同样的处理；
     * 以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想，from up to down）
     * @param ints
     */
    @Override
    public void sort(int[] ints) {
        sort(ints,0,ints.length);
    }
    private void sort(int[] arr,int start,int end) {


        if (start >= end - 1) {
            return;
        }
        int left =start;
        int right=end-1;
        // 把最左边的作为基数 并缓存起来
        int std = arr[left];
        while (left < right)
        {
            // 从右边开始查找
            // 因为左边已经空出一个位置所以从最右边开始进行比较
            while (left < right)
            {
                // 如果右边的＜ 基准数据
                if (arr[right] < std)
                {
                    //把右边数据赋值到空出的位置中
                    // 并把左位移量做加一操作
                    // 现在右边 right 位置空出
                    arr[left++] = arr[right];
                    // 退出当前循环 进入从左边比较方法
                    break;
                }
                // 若右边right位置不小于 基准则 right左移一个位置
                --right;
            }
            // 如果右边已经大于left 不用移动了
            while (left < right)
            {
                // 右边的空位已经空出
                // 左边的数和基准数的进行比较
                if (arr[left] >= std)
                {
                    // 左边的大于等于基准数 则把左边的数赋值给右边
                    // 同时左边空出一个位置
                    arr[right--] = arr[left];
                    break;
                }
                // 若右边left位置不小于 基准则 left右移一个位置
                ++left;
            }
        }
        arr[left] = std;
        sort(arr, start, left);
        sort(arr, right + 1, end);
    }
}
